package Algorithm.DynamicPlanning;

/**
 * @Author cj
 * @Date 2022/11/14 20:10
 */
public class walk {

    // 暴力破解
    public int ways1(int N, int M, int K, int P) {
        // 如果是无效参数，返回
//        if () {
//            return 0;
//        }
        return walk1(N, M, K, P);
    }

    public int walk1(int N, int cur, int rest, int P) {
        if (rest == 0) {
            return cur == P ? 1 : 0;
        }
        if (cur == 1) {
            return walk1(N, 2, rest - 1, P);
        }
        if (cur == N) {
            return walk1(N, N - 1, rest - 1, P);
        }
        return walk1(N, cur - 1, rest - 1, P) + walk1(N, cur + 1, rest - 1, P);
    }

    // 动态规划
    public int ways2(int N, int M, int K, int P) {
        // 如果是无效参数，返回
//        if () {
//            return 0;
//        }
        int[][] dp = new int[K + 1][N + 1];
        dp[0][P] = 1;
        for (int i = 1; i < K + 1; i++) {
            for (int j = 1; j < N + 1; j++) {
                if (j == 1) {
                    dp[i][j] = dp[i - 1][2];
                } else if (j == N) {
                    dp[i][j] = dp[i - 1][N - 1];
                } else {
                    dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[K][M];
    }

    // 动态规划(优化)
    public int ways3(int N, int M, int K, int P) {
        // 如果是无效参数，返回
//        if () {
//            return 0;
//        }
        int[] dp = new int[N + 1];
        dp[P] = 1;
        for (int i = 1; i < K + 1; i++) {
            // 记录左上角的值
            int leftUp = dp[1];
            for (int j = 1; j < N + 1; j++) {
                int tmp = dp[j];
                if (j == 1) {
                    dp[j] = dp[2];
                } else if (j == N) {
                    dp[j] = leftUp;
                } else {
                    dp[j] = dp[j + 1] + leftUp;
                }
                leftUp = tmp;
            }
        }
        return dp[M];
    }

}
